package myself.a012AndCollect;

import system2021.src.class15union.Code03_NumberOfIslandsII;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 叶之越
 * Description
 * Date 2021/2/1
 * Time 9:57
 * Mail 739153436@qq.com
 */
public class NumberOfIslandsII {
    public static List<Integer> numIslands21(int m, int n, int[][] positions) {
        Code03_NumberOfIslandsII.UnionFind1 uf = new Code03_NumberOfIslandsII.UnionFind1(m, n);
        // 结果集
        List<Integer> ans = new ArrayList<>();
        // 空降小岛
        for (int[] position : positions) {
            ans.add(uf.connect(position[0], position[1]));
        }
        return ans;
    }

    public static class UnionFind1 {
        private final int row;
        private final int col;
        private int[] parent;
        private int[] size;
        private int[] help;
        private int sets;

        public UnionFind1(int row, int col) {
            this.row = row;
            this.col = col;
            sets = 0;
            int len = row * col;
            parent = new int[len];
            size = new int[len];
            help = new int[len];
        }

        private int index(int row, int col) {
            return row * this.col + col;
        }

        private int find(int i) {

            int len = 0;
            while (parent[i] != i) {
                help[len++] = i;
                i = parent[i];
            }

            for (int j = 0; j <= len; j++) {
                parent[help[j]] = i;
            }
            return i;
        }

        private void union(int r1, int c1, int r2, int c2) {
            if (r1 < 0 || r1 == row || r2 < 0 || r2 == row || c1 < 0 || c1 == col || c2 < 0 || c2 == col) {
                return;
            }
            // 如果不是1的话，就不需要进行联结了
            int i1 = index(r1, c1);
            int i2 = index(r2, c2);
            // 每次进来的元素都会标记长度，如果长度为0，那么就是这个元素不是岛屿
            if (size[i1] == 0 || size[i2] == 0) {
                return;
            }

            int f1 = find(i1);
            int f2 = find(i2);
            if (f1 != f2) {
                if (size[f1] >= size[f2]) {
                    size[f1] += size[f2];
                    parent[f2] = f1;
                } else {
                    size[f2] += size[f1];
                    parent[f1] = f2;
                }
                sets--;
            }
        }

        public int connect(int r, int c) {
            int index = index(r, c);
            if (size[index] == 0) {
                parent[index] = index;
                size[index] = 1;
                sets++;
                union(r - 1, c, r, c);
                union(r + 1, c, r, c);
                union(r, c - 1, r, c);
                union(r, c + 1, r, c);
            }
            return sets;
        }
    }
}
